package com.xigua.递归深度搜索;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：
 *字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
 *每个元音 'a' 后面都只能跟着 'e'
 *每个元音 'e' 后面只能跟着 'a' 或者是 'i'
 *每个元音 'i' 后面 不能 再跟着另一个 'i'
 *每个元音 'o' 后面只能跟着 'i' 或者是 'u'
 *每个元音 'u' 后面只能跟着 'a'
 *由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。
 */
public class _1220_统计元音字母序列的树数目 {
    static char[] c = new char[]{'a','e','i','o','u'};

    public static void main(String[] args) {
        System.out.println(countVowelPermutation(40));
    }


    public static int countVowelPermutation(int n) {
        if (n==1) return 5;
        int result = 0;
        for (int i = 0; i < 5; i++) {
            result +=dfs(c[i],1,n);
            result = result;
        }
        return 1;
    }


    public static int dfs(char pre,int cur,int n){
        if (cur == n) return 1;
        int sum= 0;
        for (int i = 0; i < 5; i++) {
            if (pre == 'a' && c[i]=='e'){
                sum += dfs(c[i],cur+1,n)+1;
            }else if (pre == 'e' && (c[i] == 'a'|| c[i]=='i')){
                sum += dfs(c[i],cur+1,n);
            }else if (pre == 'i' && c[i] != 'i'){
                sum += dfs(c[i],cur+1,n);
            }else if (pre == 'o' && (c[i] == 'i' || c[i] =='u')){
                sum +=dfs(c[i],cur+1,n);
            }else if (pre == 'u' && c[i] =='a'){
                sum +=dfs(c[i],cur+1,n);
            }
        }
        return sum%1000000007;
    }


}
